#define _CRT_SECURE_NO_WARNINGS

#include "TREE.h"
#include <stdlib.h>
#include <string.h>

#define DONOTCHANGE -2
#define NOTUSED -1
#define MAXNUMVALUES 100

typedef int bool;

#define TRUE  1
#define FALSE 0

static char stringValues[MAXNUMVALUES * 3]; //Temporary storage of user input of nodevalues as a string
static int nodeValues[MAXNUMVALUES]; //Temporary storage of user input of nodevalues as numbers.
static int numValues = 0; //number of values the user input, count of nodeValues.

typedef struct cellT{
	int node[2];
	struct cellT *myParent;
	struct cellT *leftChild;
	struct cellT *middleChild;
	struct cellT *rightChild;
}cellT;


//Used to store pointers to cells below when recursing up.
struct storeT {
	struct cellT *LLChild;
	struct cellT *LChild;
	struct cellT *RChild;
	struct cellT *RRChild;
}store;

typedef struct treeCDT {
	cellT *tree;
} treeCDT;

static void printTreeC(cellT *tree);
static void *insertOneValue(cellT *cell, int value);
static bool insertValue(cellT *cell, int value);
static void askUserElements(void);
static cellT* newCellT(void);
static void sortNode(cellT *cell);
static void sortValuesInPlace(int *left, int *middle, int *right);
static bool isLeaf(cellT *cell);
static cellT *traverse(cellT *cell, int value);
static int isThreeNode(cellT cell);

static bool amIleftChild(cellT *meSelf);
static bool amImiddleChild(cellT *meSelf);
static bool amIrightChild(cellT *meSelf);
static void prepareCell(cellT *cell, int node0, int node1);
static bool amITopCell(cellT *meSelf);

static void childFullParSpace(cellT *cell);
static void topCase(cellT *cell, int value);
static void node23Full(cellT *cell);
static void resetStore(void);

static void deleteTree(cellT *tree);

static cellT *currentTopCell = NULL;

static treeADT internalTree;

treeADT newTree(){

	treeADT tree;

	tree = (treeADT)malloc(sizeof(treeCDT));
	tree->tree = newCellT();

	currentTopCell = tree->tree;

	return (tree);
}

void printTree(treeADT tree){

	printf("\n\n");
	printTreeC(currentTopCell);
	printf("\n\n");
}

void  insertElements(treeADT *tree){

	int i;
	cellT *currentCell = NULL;

	askUserElements();
	resetStore();

	for (i = 0; i < numValues; i++){
		system("CLS");
		currentCell = traverse(currentTopCell, nodeValues[i]);
		insertOneValue(currentCell, nodeValues[i]);
		printTree((*tree));
		resetStore();
	}

	(*tree)->tree = currentTopCell;
}

void simulation(){

	int i;
	cellT *storeTopCell;

	nodeValues[0] = 9;
	nodeValues[1] = 5;
	nodeValues[2] = 8;
	nodeValues[3] = 3;
	nodeValues[4] = 2;
	nodeValues[5] = 4;
	nodeValues[6] = 7;

	internalTree = (treeADT)malloc(sizeof(treeCDT));
	internalTree->tree = newCellT();

	numValues = 7;

	fflush(stdin);

	cellT *currentCell = NULL;

	storeTopCell = currentTopCell;
	currentTopCell = internalTree->tree;

	resetStore();

	for (i = 0; i < numValues; i++){
		system("CLS");
		printf("%d is inserted in the tree.", nodeValues[i]);
		currentCell = traverse(currentTopCell, nodeValues[i]);
		insertOneValue(currentCell, nodeValues[i]);
		resetStore();
		printTree(internalTree);
		printf("\n\nPress enter to continue.\n");
		getchar();
	}

	internalTree->tree = currentTopCell;

	deleteTree(internalTree->tree);
	free(internalTree);

	currentTopCell = storeTopCell;
	printf("\nDone. Press H for help or next command.\n");
}

static bool amIFull(cellT *cell){

	if (cell->node[0] != NOTUSED && cell->node[1] != NOTUSED)
		return TRUE;

	return FALSE;
}

static bool amITopCell(cellT *meSelf){

	if (meSelf->myParent == NULL)
		return TRUE;

	return FALSE;
}

static void prepareCell(cellT *cell, int node0, int node1){

	if (node0 != DONOTCHANGE)
		cell->node[0] = node0;

	if (node1 != DONOTCHANGE)
		cell->node[1] = node1;
}

static bool amIleftChild(cellT *meSelf){

	if (meSelf->myParent != NULL)
		if (meSelf == meSelf->myParent->leftChild)
			return TRUE;

	return FALSE;
}

static bool amImiddleChild(cellT *meSelf){

	if (meSelf->myParent != NULL)
		if (meSelf == meSelf->myParent->middleChild)
			return TRUE;

	return FALSE;
}

static bool amIrightChild(cellT *meSelf){

	if (meSelf->myParent != NULL)
		if (meSelf == meSelf->myParent->rightChild)
			return TRUE;

	return FALSE;
}

static void sortNode(cellT *cell){
	int temp;
	if (cell->node[0] > cell->node[1]){
		temp = cell->node[1];
		cell->node[1] = cell->node[0];
		cell->node[0] = temp;
	}
}

static void sortValuesInPlace(int *left, int *middle, int *right){

	int swap = 0;

	if (*left > *middle){
		swap = *middle;
		*middle = *left;
		*left = swap;
	}

	if (*middle > *right){
		swap = *right;
		*right = *middle;
		*middle = swap;
	}

	if (*left > *middle){
		swap = *middle;
		*middle = *left;
		*left = swap;
	}
}

static cellT* newCellT(void){

	cellT *x;
	x = (cellT*)malloc(sizeof(cellT));

	x->node[0] = NOTUSED;
	x->node[1] = NOTUSED;
	x->leftChild = NULL;
	x->middleChild = NULL;
	x->rightChild = NULL;
	x->myParent = NULL;
	return (x);
}

static void askUserElements(void){
	char *token;
	char *nextToken = NULL;
	int i;
	int node = 0;
	stringValues[0] = '\0';

	numValues = 0;

	printf("\nMaximum %d elements can be inserted at once.\n"
		"Enter an element or elements delimited by spaces: \n", MAXNUMVALUES);

	scanf("%[0-9 -]s", stringValues); // MAXNUMVALUES, stdin);

	fflush(stdin);

	token = strtok_s(stringValues, " ", &nextToken);


	for (i = 0; token != NULL && i < MAXNUMVALUES; i++){

		node = atoi(token);
		nodeValues[numValues++] = node;

		token = strtok_s(NULL, " ", &nextToken);
	}

}

static void printTreeC(cellT *tree){

	if (amITopCell(tree)
		&& tree->leftChild == NULL
		&& tree->middleChild == NULL
		&& tree->rightChild == NULL){
		printf("<Node23 (%d,%d) (NIL) (NIL) (NIL)>", tree->node[0], tree->node[1]);
		return;
	}

	if (tree->leftChild == NULL
		&& tree->middleChild == NULL
		&& tree->rightChild == NULL){

		if (tree->node[0] != -1)
			printf("(%d,%d)", tree->node[0], tree->node[1]);
		else
			printf("(NIL)");
		return;
	
	}

	printf("<Node23 (%d,%d) ", tree->node[0], tree->node[1]);

	if (tree->leftChild != NULL)
		printTreeC(tree->leftChild);
	else
		printf("(NIL)");

	printf(" ");

	if (tree->middleChild != NULL)
		printTreeC(tree->middleChild);
	else
		printf("(NIL)");

	printf(" ");

	if (tree->rightChild != NULL)
		printTreeC(tree->rightChild);
	else
		printf("(NIL)");

	printf(">");

}

static bool isLeaf(cellT *cell){

	if (cell->leftChild == NULL)
		return TRUE;

	return FALSE;
}

static cellT *traverse(cellT *cell, int value){
	if (cell == NULL || isLeaf(cell)){
		return cell;
	}

	else if (isThreeNode(*cell)){

		if (value < cell->node[0])
			traverse(cell->leftChild, value);
		else if (value > cell->node[0] && value < cell->node[1])
			traverse(cell->middleChild, value);
		else
			traverse(cell->rightChild, value);
	}
	else{
		if (value < cell->node[0])
			traverse(cell->leftChild, value);
		else
			traverse(cell->rightChild, value);
	}
}

static int isThreeNode(cellT cell){
	int i;

	for (i = 0; i < 2; i++){
		if (cell.node[i] == NOTUSED)
			return FALSE;
	}

	return TRUE;
}

static void topCase(cellT *cell, int value){

	cellT *newTopCell = newCellT();
	cellT *newLeftCell = newCellT();
	cellT *newRightCell = newCellT();

	sortValuesInPlace(&cell->node[0], &value, &cell->node[1]);

	prepareCell(newTopCell, value, NOTUSED);
	prepareCell(newLeftCell, cell->node[0], NOTUSED);
	prepareCell(newRightCell, cell->node[1], NOTUSED);

	newTopCell->leftChild = newLeftCell;
	newTopCell->rightChild = newRightCell;

	newLeftCell->myParent = newTopCell;
	newRightCell->myParent = newTopCell;

	newLeftCell->leftChild = store.LLChild;
	newLeftCell->rightChild = store.LChild;

	newRightCell->leftChild = store.RChild;
	newRightCell->rightChild = store.RRChild;

	if (store.LLChild != NULL){
		store.LLChild->myParent = newLeftCell;
		store.LChild->myParent = newLeftCell;
		store.RChild->myParent = newRightCell;
		store.RRChild->myParent = newRightCell;
	}

	free(currentTopCell);
	currentTopCell = newTopCell;
}

static void childFullParSpace(cellT *cell){

		cellT *newMiddleCell = newCellT();

		//right : left
		prepareCell(newMiddleCell, amIrightChild(cell) == TRUE ? cell->node[0] : cell->node[1], NOTUSED);
		prepareCell(cell, amIrightChild(cell) == TRUE ? cell->node[1]: cell->node[0], NOTUSED);
		cell->myParent->middleChild = newMiddleCell;

		newMiddleCell->myParent = cell->myParent;

		//right
		if (amIrightChild(cell)){
			newMiddleCell->leftChild = store.LLChild;
			newMiddleCell->rightChild = store.LChild;
			//right: new parent for moved nodes
			if (store.LLChild != NULL){
				store.LLChild->myParent = newMiddleCell;
				store.LChild->myParent = newMiddleCell;

				store.RChild->myParent = cell;
				store.RRChild->myParent = cell;
			}

			cell->leftChild = store.RChild; 
			cell->rightChild = store.RRChild;

		}

		//left 
		if (amIleftChild(cell)){
			newMiddleCell->leftChild = store.RChild; 
			newMiddleCell->rightChild = store.RRChild;
			//left: new parent for moved nodes
			if (store.RRChild != NULL){
				store.RRChild->myParent = newMiddleCell;
				store.RChild->myParent = newMiddleCell;

				store.LLChild->myParent = cell;
				store.LChild->myParent = cell;
			}

			cell->leftChild = store.LLChild;
			cell->rightChild = store.LChild;

		}


		cell->middleChild = NULL;
}

static void node23Full(cellT *cell){

		cellT *hookCell = newCellT();

		hookCell->myParent = cell->myParent;

		//*LCell = *cell;

		if (amIleftChild(cell)){
			prepareCell(hookCell, cell->node[1], NOTUSED);

			cell->leftChild = store.LLChild;
			cell->rightChild = store.LChild;
			hookCell->leftChild = store.RChild;
			hookCell->rightChild = store.RRChild;

			store.LLChild = cell;
			store.LChild = hookCell;
			store.RChild = cell->myParent->middleChild;
			store.RRChild = cell->myParent->rightChild;

			prepareCell(cell, cell->node[0], NOTUSED);
		}


		if (amImiddleChild(cell)){
			prepareCell(hookCell, cell->node[1], NOTUSED);

			cell->leftChild = store.LLChild;
			cell->rightChild = store.LChild;
			hookCell->leftChild = store.RChild;
			hookCell->rightChild = store.RRChild;

			store.LLChild = cell->myParent->leftChild;
			store.LChild = cell;
			store.RChild = hookCell;
			store.RRChild = cell->myParent->rightChild;

			prepareCell(cell, cell->node[0], NOTUSED);
		}

		if (amIrightChild(cell)){
			prepareCell(hookCell, cell->node[0], NOTUSED);

			hookCell->leftChild = store.LLChild;
			hookCell->rightChild = store.LChild;
			cell->leftChild = store.RChild;
			cell->rightChild = store.RRChild;


			store.LLChild = cell->myParent->leftChild;
			store.LChild = cell->myParent->middleChild;
			store.RChild = hookCell;
			store.RRChild = cell;

			prepareCell(cell, cell->node[1], NOTUSED);
		}

		cell->middleChild = NULL;


}

static bool insertValue(cellT *cell, int value){

	if (cell->node[0] == NOTUSED){
		cell->node[0] = value;
		return TRUE;
	}

	if (cell->node[1] == NOTUSED){
		cell->node[1] = value;
		sortNode(cell);
		return TRUE;
	}

	return FALSE;
}

static void *insertOneValue(cellT *cell, int value){

	if (value == cell->node[0] || value == cell->node[1])
		return;

	if (insertValue(cell, value))
		return;

	//////////////////////////////////////////////

	//top-case, new topcell
	if (amIFull(cell) && amITopCell(cell)){
		topCase(cell, value);
		return;
	}

	//2-node child full, parent have space
	if (amIFull(cell) && !amIFull(cell->myParent)){
		sortValuesInPlace(&cell->node[0], &value, &cell->node[1]);
		childFullParSpace(cell);
		insertOneValue(cell->myParent, value);
		return;
	}

	//23node full
	if (amIFull(cell) && amIFull(cell->myParent)){
		sortValuesInPlace(&cell->node[0], &value, &cell->node[1]);
		node23Full(cell);
		insertOneValue(cell->myParent, value);
		return;
	}
	////////////////////////////////////////

	return;
}

static void resetStore(void){

	store.LLChild = NULL;
	store.LChild = NULL;
	store.RChild = NULL;
	store.RRChild = NULL;
}

static void deleteTree(cellT *tree){


	if (tree->leftChild == NULL
		&& tree->middleChild == NULL
		&& tree->rightChild == NULL){
		free(tree);
		return;
	}

	if (tree->leftChild != NULL)
		deleteTree(tree->leftChild);


	if (tree->middleChild != NULL)
		deleteTree(tree->middleChild);


	if (tree->rightChild != NULL)
		deleteTree(tree->rightChild);

}